Combinatorial auctions have been suggested as a means to raise efficiency in multi-item negotiations with complementarities among goods because they can be applied in procurement, energy markets, transportation, and the sale of spectrum auctions. The combinatorial clock (CC) auction has become very popular in these markets for its simplicity and for its highly usable price discovery, derived by the use of linear prices. Unfortunately, no equilibrium bidding strategies are known. Given the importance of the CC auction in the field, it is highly desirable to understand whether there are efficient versions of the CC auction providing a strong game theoretical solution concept. So far, equilibrium strategies have only been found for combinatorial auctions with nonlinear and personalized prices for very restricted sets of bidder valuations. We introduce an extension of the CC auction, the CC+ auction, and show that it actually leads to efficient outcomes in an ex post equilibrium for general valuations with only linear ask prices. We also provide a theoretical analysis on the worst case efficiency of the CC auction, which highlights situations in which the CC leads to highly inefficient outcomes. As in other theoretical models of combinatorial auctions, bidders in the field might not be able to follow the equilibrium strategies suggested by the game-theoretical predictions. Therefore, we complement the theoretical findings with results from computational and laboratory experiments using realistic value models. The experimental results illustrate that the CC+ auction can have a significant impact on efficiency compared to the CC auction.
Combinatorial auctions are used in a variety of application domains, such as transportation or industrial procurement, using a variety of bidding languages and different allocation constraints. This flexibility in the bidding languages and the allocation constraints is essential in these domains but has not been considered in the theoretical literature so far. In this paper, we analyze different pricing rules for ascending combinatorial auctions that allow for such flexibility: winning levels and deadness levels. We determine the computational complexity of these pricing rules and show that deadness levels actually satisfy an ex post equilibrium, whereas winning levels do not allow for a strong game theoretical solution concept. We investigate the relationship of deadness levels and the simple price update rules used in efficient ascending combinatorial auction formats. We show that ascending combinatorial auctions with deadness level pricing rules maintain a strong game theoretical solution concept and reduce the number of bids and rounds required at the expense of higher computational effort. The calculation of exact deadness levels is a II<sup>P</sup><sub>2</sub> -complete problem. Nevertheless, numerical experiments show that for mid-sized auctions this is a feasible approach. The paper provides a foundation for allocation constraints in combinatorial auctions and a theoretical framework for recent Information Systems contributions in this field.
Combinatorial auctions are used for the efficient allocation of heterogeneous goods and services. They require appropriate software platforms that provide automated winner determination and decision support for bidders. Several promising ascending combinatorial auction formats have been developed throughout the past few years based on primal-dual algorithms and linear programming theory. The ascending proxy auction and iBundle result in Vickrey payoffs when the coalitional value function satisfies buyer submodularity conditions and bidders bid their best responses. These auction formats are based on nonlinear and personalized ask prices. In addition, there are a number of designs with linear prices that have performed well in experiments, the approximate linear prices auction, and the combinatorial clock auction. In this paper, we provide the results of lab experiments that tested these different auction formats in the same setting. We analyze aggregate metrics such as efficiency and auctioneer revenue for small- and medium-sized value models. In addition, we provide a detailed analysis not only of aggregate performance metrics but also of individual bidding behaviour under alternative combinatorial auction formats.
Electronic markets have been a core topic of information systems (IS) research for last three decades. We focus on a more recent phenomenon: smart markets. This phenomenon is starting to draw considerable interdisciplinary attention from the researchers in computer science, operations research, and economics communities. The objective of this commentary is to identify and outline fruitful research areas where IS researchers can provide valuable contributions. The idea of smart markets revolves around using theoretically supported computational tools to both understand the characteristics of complex trading environments and multiechelon markets and help human decision makers make real-time decisions in these complex environments. We outline the research opportunities for complex trading environments primarily from the perspective of design of computational tools to analyze individual market organization and provide decision support in these complex environments. In addition, we present broad research opportunities that computational platforms can provide, including implications for policy and regulatory research.
Iterative combinatorial auctions (ICAs) are IT-based economic mechanisms where bidders submit bundle bids in a sequence and an auctioneer computes allocations and ask prices in each auction round. The literature in this field provides equilibrium analysis for ICAs with nonlinear personalized prices under strong assumptions on bidders' strategies. Linear pricing has performed very well in the lab and in the field. In this paper, we compare three selected linear price ICA formats based on allocative efficiency and revenue distribution using different bidding strategies and bidder valuations. The goal of this research is to benchmark different ICA formats and design and analyze new auction rules for auctions with pseudodual linear prices. The multi-item and discrete nature of linear price iterative combinatorial auctions and the complex price calculation schemes defy much of the traditional game theoretical analysis in this field. Computational methods can be of great help in exploring potential auction designs and analyzing the virtues of various design options. In our simulations, we found that ICA designs with linear prices performed very well for different valuation models even in cases of high synergies among the valuations. There were, however, significant differences in efficiency and in the revenue distributions of the three ICA formats. Heuristic bidding strategies using only a few of the best bundles also led to high levels of efficiency. We have also identified a number of auction rules for ask price calculation and auction termination that have shown to perform very well in the simulations.